/**
 * 二叉搜索树节点
 */
class BSTNode {
    constructor(key) {
        this.key = key
        this.left = null
        this.right = null
    }
}

const ComparisonResults = {
    BIGGER: 'bigger',
    SMALLER: 'smaller',
    EQUAL: 'equal'
}

/**
 * 二叉搜索树
 */
export default class BinarySearchTree {
    #root = null

    /**
     * 想二叉树中插入节点
     * @param {number} key 
     * @returns {BSTNode} root
     */
    insert(key) {
        if (this.#root === null) {
            this.#root = new BSTNode(key)  // 如果是一课空树，将插入的树节点作为根节点
        } else {
            this.#insertNode(key, this.#root) // 否则，向根节点下方插入节点
        }
        return this.#root
    }

    /**
     * 向指定树节点下方插入子节点
     * @param {number} key 
     * @param {BSTNode} node 
     */
    #insertNode(key, node) {
        if (this.#compare(key, node.key) === ComparisonResults.SMALLER) { // 如果要插入的值小于指定节点的值
            if (node.left === null) { // 如果指定节点的左枝为空
                node.left = new BSTNode(key) // 将该值包装成节点放在指定根节点的左枝上
            } else {
                this.#insertNode(key, node.left) // 否则继续将该值放在指定节点的左枝下方
            }
        } else if (this.#compare(key, node.key) === ComparisonResults.BIGGER) { // 如果要插入的值大于指定节点的值
            if (node.right === null) { // 如果指定节点的右枝为空
                node.right = new BSTNode(key) // 将该值包装成节点放在指定根节点的右枝上
            } else {
                this.#insertNode(key, node.right) // 否则继续将该值放在指定节点的右枝下方
            }
        }
    }

    /**--------------------------------------------------------遍历 start------------------------------------------------------- */
    /**
     * 比较两个值的大小
     * @param {number} keyA 
     * @param {number} keyB 
     * @returns {string} 'bigger' | 'smaller' | 'equal'
     */
    #compare(keyA, keyB) {
        if (keyA > keyB) {
            return ComparisonResults.BIGGER
        }
        if (keyA < keyB) {
            return ComparisonResults.SMALLER
        }
        if (keyA === keyB) {
            return ComparisonResults.EQUAL
        }
    }

    /**
     * 中序遍历（按照 search tree 节点值大小由小至大遍历）
     * @param {Function} callback 
     */
    inOrderMap(callback) {
        this.#inOrderMapNode(this.#root, callback)
    }

    /**
     * 中序深入节点
     * @param {BSTNode} node 
     * @param {Function} callback 
     */
    #inOrderMapNode(node, callback) {

        if (node != null) { // 如果输入节点不为空
            this.#inOrderMapNode(node.left, callback) // 继续向左侧深入该节点
            callback(node) // 如果该节点左节点已遍历完毕，执行回调函数
            this.#inOrderMapNode(node.right, callback) // 继续向右侧深入该节点
        }
    }

    /**
     * 先序遍历（顺延左支遍历所有节点）
     * @param {Function} callback 
     */
    preOrderMap(callback) {
        this.#preOrderMapNode(this.#root, callback)
    }

    /**
     * 先序深入节点
     * @param {BSTNode} node 
     * @param {Function} callback 
     */
    #preOrderMapNode(node, callback) {
        if (node !== null) {
            callback(node)
            this.#preOrderMapNode(node.left, callback)
            this.#preOrderMapNode(node.right, callback)
        }
    }

    /**
     * 后序遍历（由左底层往右至上遍历所有节点）
     * @param {Function} callback 
     */
    postOrderMap(callback) {
        this.#postOrderMapNode(this.#root, callback)
    }

    /**
     * 后序深度节点
     * @param {BSTNode} node 
     * @param {Function} callback 
     */
    #postOrderMapNode(node, callback) {
        if (node != null) {
            this.#postOrderMapNode(node.left, callback)
            this.#postOrderMapNode(node.right, callback)
            callback(node)
        }
    }
    /**--------------------------------------------------------遍历 end------------------------------------------------------- */

    /**
     * 获取树种最小的key
     * @returns {number} Minimum key
     */
    getMinimum() {
        return this.#min(this.#root)
    }

    /**
     * 获取指定节点下最小的key
     * @param {BSTNode} node 
     * @returns {number} Minimum key
     */
    #min(node) {
        let minimumNode = node
        while (minimumNode.left != null) { // 节点一路向左深入，取最左侧的节点对应key即为最小值
            minimumNode = minimumNode.left
        }
        return minimumNode.key
    }

    /**
     * 获取指定节点下key最小的节点
     * @param {BSTNode} node 
     * @returns {BSTNode} node
     */
    #minNode(node) {
        let minimumNode = node
        while (minimumNode.left != null) { // 节点一路向左深入，取最左侧的节点对应key即为最小值
            minimumNode = minimumNode.left
        }
        return minimumNode
    }

    /**
     * 获取树种最大的key
     * @returns {number} Maxmum key
     */
    getMaxmum() {
        return this.#max(this.#root)
    }

    /**
     * 获取指定节点下最大的key
     * @param {BSTNode} node 
     * @returns {number} Maxmum key
     */
    #max(node) {
        let maxmumNode = node
        while (maxmumNode.right != null) {// 节点一路向右深入，取最右侧的节点对应key即为最大值
            maxmumNode = maxmumNode.right
        }
        return maxmumNode.key
    }

    /**
     * 检查二叉树中是否包含指定的key
     * @param {number} key 
     * @returns {boolean} true or false
     */
    includes(key) {
        return !!this.#search(key, this.#root)
    }

    /**
     * 搜索二叉树节点下指定key的节点
     * @param {number} key 
     * @param {BSTNode} node 
     * @returns {BSTNode} note with the key
     */
    #search(key, node) {
        if (node == null) {
            return null
        }
        if (key === node.key) {
            return node
        } else if (key < node.key) {
            return this.#search(key, node.left)
        } else {
            return this.#search(key, node.right)
        }
    }

    /**
     * 删除输入key对应的节点
     * @param {number} key 
     */
    remove(key) {
        this.#root = this.#removeNode(this.#root, key)
    }

    /**
     * 删除指定node下输入的key所对应的节点
     * @param {BSTNode} node 
     * @param {number} key 
     * @returns {BSTNode} note with the key
     */
    #removeNode(node, key) {
        if (node == null) {
            return null
        }
        if (this.#compare(key, node.key) === ComparisonResults.SMALLER) {
            node.left = this.#removeNode(node.left, key)
            return node
        }
        if (this.#compare(key, node.key) === ComparisonResults.BIGGER) {
            node.right = this.#removeNode(node.right, key)
            return node
        }
        if (this.#compare(key, node.key) === ComparisonResults.EQUAL) {
            if (node.left == null && node.right == null) {
                return null
            } else if (node.right == null) {
                return node.left
            } else if (node.left == null) {
                return node.right
            } else {
                const minNodeOfTheRightBranch = this.#minNode(node.right)
                node.key = minNodeOfTheRightBranch.key
                node.right = this.#removeNode(node.right, minNodeOfTheRightBranch.key)
                return node
            }
        }
    }
}